English Version

你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。

示例 1：

输入： pattern = "abba", value = "dogcatcatdog" 输出： true 

示例 2：

输入： pattern = "abba", value = "dogcatcatfish" 输出： false 

示例 3：

输入： pattern = "aaaa", value = "dogcatcatdog" 输出： false 

示例 4：

输入： pattern = "abba", value = "dogdogdogdog" 输出： true 解释： "a"="dogdog",b=""，反之也符合规则 

提示：

• 0 <= len(pattern) <= 1000
• 0 <= len(value) <= 1000
• 你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。

我们先统计出模式串 $pattern$ 中 'a' 和 'b' 的个数，分别为 $cnt[0]$ 和 $cnt[1]$。记字符串 $value$ 的长度为 $n$。

如果 $cnt[0]=0$，说明模式串中只包含字符 'b'，那么我们需要判断 $n$ 是否是 $cnt[1]$ 的倍数，以及 $value$ 是否可以分割成 $cnt[1]$ 个长度为 $n/cnt[1]$ 的子串，且这些子串都相同。如果不满足，直接返回 $false$ 即可。

如果 $cnt[1]=0$，说明模式串中只包含字符 'a'，那么我们需要判断 $n$ 是否是 $cnt[0]$ 的倍数，以及 $value$ 是否可以分割成 $cnt[0]$ 个长度为 $n/cnt[0]$ 的子串，且这些子串都相同。如果不满足，直接返回 $false$ 即可。

接下来，我们记字符 'a' 所匹配的字符串的长度 $la$，字符 'b' 所匹配的字符串的长度 $lb$。那么有 $la \times cnt[0] + lb \times cnt[1] = n$。如果我们枚举 $la$，就可以知道 $lb$ 的值了。因此我们可以枚举 $la$，只需要判断是否存在一个整数 $lb$，满足上述等式即可。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $value$ 的长度。

classSolution: defpatternMatching(self, pattern: str, value: str) ->bool: defcheck(la: int, lb: int) ->bool: i=0a, b="", ""forcinpattern: ifc=="a": ifaandvalue[i : i+la] !=a: returnFalsea=value[i : i+la] i+=laelse: ifbandvalue[i : i+lb] !=b: returnFalseb=value[i : i+lb] i+=lbreturna!=bn=len(value) cnt=Counter(pattern) ifcnt["a"] ==0: returnn%cnt["b"] ==0andvalue[: n//cnt["b"]] *cnt["b"] ==valueifcnt["b"] ==0: returnn%cnt["a"] ==0andvalue[: n//cnt["a"]] *cnt["a"] ==valueforlainrange(n+1): ifla*cnt["a"] >n: breaklb, mod=divmod(n-la*cnt["a"], cnt["b"]) ifmod==0andcheck(la, lb): returnTruereturnFalse

classSolution { privateStringpattern; privateStringvalue; publicbooleanpatternMatching(Stringpattern, Stringvalue) { this.pattern = pattern; this.value = value; int[] cnt = newint[2]; for (charc : pattern.toCharArray()) { ++cnt[c - 'a']; } intn = value.length(); if (cnt[0] == 0) { returnn % cnt[1] == 0 && value.substring(0, n / cnt[1]).repeat(cnt[1]).equals(value); } if (cnt[1] == 0) { returnn % cnt[0] == 0 && value.substring(0, n / cnt[0]).repeat(cnt[0]).equals(value); } for (intla = 0; la <= n; ++la) { if (la * cnt[0] > n) { break; } if ((n - la * cnt[0]) % cnt[1] == 0) { intlb = (n - la * cnt[0]) / cnt[1]; if (check(la, lb)) { returntrue; } } } returnfalse; } privatebooleancheck(intla, intlb) { inti = 0; Stringa = null, b = null; for (charc : pattern.toCharArray()) { if (c == 'a') { if (a != null && !a.equals(value.substring(i, i + la))) { returnfalse; } a = value.substring(i, i + la); i += la; } else { if (b != null && !b.equals(value.substring(i, i + lb))) { returnfalse; } b = value.substring(i, i + lb); i += lb; } } return !a.equals(b); } }

classSolution { public:boolpatternMatching(string pattern, string value) { int n = value.size(); int cnt[2]{}; for (char c : pattern) { cnt[c - 'a']++; } if (cnt[0] == 0) { return n % cnt[1] == 0 && repeat(value.substr(0, n / cnt[1]), cnt[1]) == value; } if (cnt[1] == 0) { return n % cnt[0] == 0 && repeat(value.substr(0, n / cnt[0]), cnt[0]) == value; } auto check = [&](int la, int lb) { int i = 0; string a, b; for (char c : pattern) { if (c == 'a') { if (!a.empty() && a != value.substr(i, la)) { returnfalse; } a = value.substr(i, la); i += la; } else { if (!b.empty() && b != value.substr(i, lb)) { returnfalse; } b = value.substr(i, lb); i += lb; } } return a != b; }; for (int la = 0; la <= n; ++la) { if (la * cnt[0] > n) { break; } if ((n - la * cnt[0]) % cnt[1] == 0) { int lb = (n - la * cnt[0]) / cnt[1]; if (check(la, lb)) { returntrue; } } } returnfalse; } string repeat(string s, int n) { string ans; while (n--) { ans += s; } return ans; } };

funcpatternMatching(patternstring, valuestring) bool { cnt:= [2]int{} for_, c:=rangepattern { cnt[c-'a']++ } n:=len(value) ifcnt[0] ==0 { returnn%cnt[1] ==0&&strings.Repeat(value[:n/cnt[1]], cnt[1]) ==value } ifcnt[1] ==0 { returnn%cnt[0] ==0&&strings.Repeat(value[:n/cnt[0]], cnt[0]) ==value } check:=func(la, lbint) bool { i:=0a, b:="", ""for_, c:=rangepattern { ifc=='a' { ifa!=""&&value[i:i+la] !=a { returnfalse } a=value[i : i+la] i+=la } else { ifb!=""&&value[i:i+lb] !=b { returnfalse } b=value[i : i+lb] i+=lb } } returna!=b } forla:=0; la<=n; la++ { ifla*cnt[0] >n { break } if (n-la*cnt[0])%cnt[1] ==0 { lb:= (n-la*cnt[0]) /cnt[1] ifcheck(la, lb) { returntrue } } } returnfalse }

functionpatternMatching(pattern: string,value: string): boolean{constcnt: number[]=[0,0];for(constcofpattern){cnt[c==='a' ? 0 : 1]++;}constn=value.length;if(cnt[0]===0){returnn%cnt[1]===0&&value.slice(0,(n/cnt[1])|0).repeat(cnt[1])===value;}if(cnt[1]===0){returnn%cnt[0]===0&&value.slice(0,(n/cnt[0])|0).repeat(cnt[0])===value;}constcheck=(la: number,lb: number)=>{leti=0;leta='';letb='';for(constcofpattern){if(c==='a'){if(a&&a!==value.slice(i,i+la)){returnfalse;}a=value.slice(i,(i+=la));}else{if(b&&b!==value.slice(i,i+lb)){returnfalse;}b=value.slice(i,(i+=lb));}}returna!==b;};for(letla=0;la<=n;++la){if(la*cnt[0]>n){break;}if((n-la*cnt[0])%cnt[1]===0){constlb=((n-la*cnt[0])/cnt[1])|0;if(check(la,lb)){returntrue;}}}returnfalse;}

classSolution{privatevarpattern:String=""privatevarvalue:String=""func patternMatching(_ pattern:String, _ value:String)->Bool{self.pattern = pattern self.value = value varcnt=[Int](repeating:0, count:2)forcin pattern {cnt[Int(c.asciiValue! - Character("a").asciiValue!)]+=1}letn= value.count ifcnt[0]==0{return n % cnt[1]==0 && String(repeating:String(value.prefix(n / cnt[1])), count:cnt[1])== value }ifcnt[1]==0{return n % cnt[0]==0 && String(repeating:String(value.prefix(n / cnt[0])), count:cnt[0])== value }forlain0...n {if la * cnt[0]> n {break}if(n - la * cnt[0])% cnt[1]==0{letlb=(n - la * cnt[0])/ cnt[1]ifcheck(la, lb){returntrue}}}returnfalse}privatefunc check(_ la:Int, _ lb:Int)->Bool{vara:String?=nilvarb:String?=nilvarindex= value.startIndex forcin pattern {if c =="a"{letend= value.index(index, offsetBy: la)iflet knownA = a {if knownA !=value[index..<end]{returnfalse}}else{ a =String(value[index..<end])} index = end }else{letend= value.index(index, offsetBy: lb)iflet knownB = b {if knownB !=value[index..<end]{returnfalse}}else{ b =String(value[index..<end])} index = end }}return a != b }}